package week98;

import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int res = solution.sumSubseqWidths(new int[]{2, 1, 3});
        System.out.println(res);
        assert res == 6;
        res = solution.sumSubseqWidths(new int[]{5, 69, 89, 92, 31, 16, 25, 45, 63, 40, 16, 56, 24, 40, 75, 82, 40, 12
                , 50, 62, 92, 44, 67, 38, 92, 22, 91, 24, 26, 21, 100, 42, 23, 56, 64, 43, 95, 76, 84, 79, 89, 4, 16, 94, 16, 77, 92, 9, 30, 13});

        System.out.println(res);
        assert res == 857876214;
//        System.out.println(solution.findAndReplacePattern(new String[]{"abc", "deq", "mee", "aqq", "dkd", "ccc"}, "abb"));
        /*
        int[] res = solution.fairCandySwap(new int[]{1, 1}, new int[]{2, 2});
        System.out.println(res[0] + "," + res[1]);

        res = solution.fairCandySwap(new int[]{1, 2}, new int[]{2, 3});
        System.out.println(res[0] + "," + res[1]);
        res = solution.fairCandySwap(new int[]{1, 2}, new int[]{2, 3});
        System.out.println(res[0] + "," + res[1]);
        res = solution.fairCandySwap(new int[]{2}, new int[]{1, 3});
        System.out.println(res[0] + "," + res[1]);
        res = solution.fairCandySwap(new int[]{1, 2, 5}, new int[]{2, 4});
        System.out.println(res[0] + "," + res[1]);*/
    }

    public int sumSubseqWidths(int[] A) {
        Arrays.sort(A);
        long res = 0;
        BigInteger two = new BigInteger("2");
        long NUM = (int) (Math.pow(10, 9) + 7);
        BigInteger resmaining = new BigInteger(String.valueOf(NUM));
        for (int i = 0; i < A.length - 1; i++) {
            for (int j = i + 1; j < A.length; j++) {
                int width = A[j] - A[i];
                if (width == 0) continue;
                else {
                    BigInteger temp = two.pow(j - i - 1);
                    long len = temp.remainder(resmaining).intValue();
                    res += width * len;
                    if (res > NUM) {
                        res %= NUM;
                    }
                }
            }
        }
        res %= NUM;
        return (int)res;
    }

    public List<String> findAndReplacePattern(String[] words, String pattern) {
        List<String> list = new LinkedList<>();
        for (String word : words) {
            if (word.length() != pattern.length()) continue;
            boolean flag = true;
            int[] code = new int[27];
            int[] decode = new int[27];
            for (int i = 0; i < word.length(); i++) {
                char c1 = word.charAt(i);
                char c2 = pattern.charAt(i);
                if (code[c1 - 'a' + 1] == 0 && decode[c2 - 'a' + 1] == 0) {
                    code[c1 - 'a' + 1] = c2 - 'a' + 1;
                    decode[c2 - 'a' + 1] = c1 - 'a' + 1;
                } else {
                    if (!(code[c1 - 'a' + 1] != 0 && decode[c2 - 'a' + 1] == (c1 - 'a' + 1))) {
                        flag = false;
                        break;
                    }
                }
            }
            if (flag) list.add(word);
        }
        return list;
    }

    public int[] fairCandySwap(int[] A, int[] B) {
        int[] candyA = new int[100001];
        int[] candyB = new int[100001];
        int countA = 0;
        int countB = 0;
        for (int i : A) {
            countA += i;
            candyA[i]++;
        }
        for (int i : B) {
            countB += i;
            candyB[i]++;
        }
        int delta = countA - countB;
        delta = delta / 2;
        for (int i = 0; i < candyA.length; i++) {
            int index = i - delta;
            if (candyA[i] > 0 && index >= 0 && index < candyB.length && candyB[index] != 0) {
                return new int[]{i, index};
            }
        }
        return null;
    }
}
